package graph;

import java.util.*;

public class GraphTopology_231113 {
    public static List<Node<Integer>> topoSort(Graph<Integer> graph) {
        // Graph抽象中包含了入度
        // 存储所有节点的入度
        Map<Node<Integer>, Integer> inMap = new HashMap<>();
        // 存储入度为0的点
        Deque<Node<Integer>> zeroQ = new ArrayDeque<>();
        // 记录所有点的入度，并初始化入度为0的队列
        graph.nodeMap.values().forEach(node -> {
            inMap.put(node, node.in);
            if (node.in == 0) {
                zeroQ.offer(node);
            }
        });

        // 拓扑序结果
        List<Node<Integer>> result = new ArrayList<>();
        while (!zeroQ.isEmpty()) {
            Node<Integer> top = zeroQ.poll();
            result.add(top);
            // 遍历所有相邻的节点，消除当前入度为0的节点在图中的影响
            top.nextNodes.forEach(nextNode -> {
                inMap.put(nextNode, inMap.getOrDefault(nextNode, 1) - 1);
                if (inMap.get(nextNode) == 0) {
                    zeroQ.offer(nextNode);
                }
            });
        }
        return result;
    }
}
